package problem101_Symmetric_Tree;

import java.util.LinkedList;
import java.util.Queue;

import problem95_UniqueBinarySearchTreesII.MySolution.TreeNode;

public class MySolution {
	public boolean isSymmetric(TreeNode root) {
		return bfs(root,root);
    }
	
	private boolean bfs(TreeNode left,TreeNode right){
		if(left==null && right==null)
			return true;
		else if(left==null || right==null)
			return false;
		return left.val==right.val&&bfs(left.left,right.right)&&bfs(left.right,right.left);
	}
	
	public boolean isSymmetricNonRecursive(TreeNode root) {
		if(root==null)	return true;
		 Queue<TreeNode> queue=new LinkedList<>();
		 queue.add(root.left);
		 queue.add(root.right);
		 while(!queue.isEmpty()){
			 TreeNode left=queue.poll();
			 TreeNode right=queue.poll();
			 if(left==null&&right==null) continue;
			 if(left==null||right==null||left.val!=right.val)
				 return false;
			 queue.add(left.left);
			 queue.add(right.right);
			 queue.add(left.right);
			 queue.add(right.left);
		 }
		 return true;
	}
}
